package com.cheung.leetcode.binarysearch;

public class LC69 {


    public static int mySqrt(int x) {
        // 特殊值单独计算了
        if (x == 0 || x == 1) {
            return x;
        }

        // 对于其他值，0和x都是取不到的值，假设目标值是target
        // 1到target标蓝，target+1到x-1标红
        // 跳出循环的条件就是left+1==right
        // isBlue() 就是 mid ==（left+right）/2 的平方<=x
        int left = 0;
        int right = x;
        while (left + 1 != right) {
            int mid = (left + right) / 2;
            if (x / mid >= mid) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;

    }

    public static void main(String[] args) {
        System.out.println(mySqrt(7));
        System.out.println(mySqrt(8));
        System.out.println(mySqrt(9));
        System.out.println(mySqrt(15));
        System.out.println(mySqrt(16));
        System.out.println(mySqrt(17));
    }
}
